#include<iostream>
#include<vector>
using namespace std;

const int N=1e6+10;

vector<int> primes;
bool st[N+1];
auto Init=[]
{
    for(int i=2;i<=N;++i)
    {
        if(!st[i])
            primes.emplace_back(i);
        for(int j=0;primes[j]<=N/i;++j)
        {
            st[primes[j]*i]=true;
            if(i%primes[j]==0) break;
        }
    }
    return 0;
}();

class Solution {
public:
    vector<vector<int>> findPrimePairs(int n) {
        vector<vector<int>> res;
        if(n%2)
        {
            if(n>4&&!st[n-2])
            {
                res.push_back({2,n-2});
            }
            return res;
        }
        
        for(int x:primes)
        {
            int y=n-x;
            if(y<x) break;
            if(!st[y]) res.push_back({x,y});
        }
        return res;
    }
};